package problems.daily;

/**
 * 1806. 还原排列的最少操作步数
 * <p>https://leetcode.cn/problems/minimum-number-of-operations-to-reinitialize-a-permutation/</p>
 *
 * @author habitplus
 * @since 9:25, 2023/1/9
 */
public class DT1806 {
    /**
     * <p>直接模拟</p>
     * <li>时间复杂度：O(n^2)</li>
     * <li>空间复杂度：O(n)</li>
     */
    public int reinitializePermutation1(int n) {
        int[] arr = new int[n];
        int[] tmpArr = new int[n];
        int step = 0;

        for (int i = 0; i < n; ++i) arr[i] = i;

        do {
            for (int i = 0; i < n; ++i) {
                if (i % 2 == 0) tmpArr[i] = arr[i / 2];
                else tmpArr[i] = arr[n / 2 + (i - 1) / 2];
            }
            System.arraycopy(tmpArr, 0, arr, 0, n);
            ++step;
        } while (arr[1] != 1);

        return step;
    }

    /**
     * <p>数学法</p>
     * <li>时间复杂度：O(n)</li>
     * <li>空间复杂度：O(1)</li>
     */
    public int reinitializePermutation(int n) {
        if (n == 2) {
            return 1;
        }
        int step = 1, pow2 = 2;
        while (pow2 != 1) {
            step++;
            pow2 = pow2 * 2 % (n - 1);
        }
        return step;
    }


    public static void main(String[] args) {
        DT1806 test = new DT1806();
        int ans;
        long ed;
        long st1 = System.currentTimeMillis();
        for (int i = 2; i <= 1000; i += 2) {
            long st = System.currentTimeMillis();
            ans = test.reinitializePermutation(i);
            ed = System.currentTimeMillis();
            System.out.printf("==>i=%d, ans=%d, 耗时 %dms%n", i, ans, (ed - st));
        }
        ed = System.currentTimeMillis();
        System.out.println("共耗时 " + (ed - st1) + "ms");
    }
}
